package com.example.Arithmetic.Arithmetic;

import java.util.LinkedList;
import java.util.List;

/**
 * 日期：2023/12/29
 * 时间：13:44
 * 描述：图的DFS深度优先遍历
 */
public class FigureDfs {
    public static void main(String[] args) {
        Vertex v1 = new Vertex("v1");
        Vertex v2 = new Vertex("v2");
        Vertex v3 = new Vertex("v3");
        Vertex v4 = new Vertex("v4");
        Vertex v5 = new Vertex("v5");
        Vertex v6 = new Vertex("v6");

        v1.edges = List.of(new Edge(v3), new Edge(v2), new Edge(v6));
        v2.edges = List.of(new Edge(v4));
        v3.edges = List.of(new Edge(v4), new Edge(v6));
        v4.edges = List.of(new Edge(v5));
        v5.edges = List.of();
        v6.edges = List.of(new Edge(v5));

        dfs2(v1);
    }

    //    递归遍历
    private static void dfs1(Vertex v1) {
        v1.visited = true;
        System.out.println(v1.name);
        for (Edge e : v1.edges) {
            if (!e.linked.visited) {
                dfs1(e.linked);
            }
        }
    }

    //    栈实现遍历
    private static void dfs2(Vertex v1) {
        LinkedList<Vertex> list = new LinkedList();
        list.add(v1);
        while (!list.isEmpty()) {
            Vertex pop = list.pop();
            System.out.println(pop.name);
            pop.visited = true;
            for (Edge e : pop.edges) {
                if (!e.linked.visited) {
                    list.push(e.linked);
                }
            }
        }
    }
}
